package leetcode;

/**
 * 516. 最长回文子序列     https://leetcode.cn/problems/longest-palindromic-subsequence/
 */
public class LeetCode516 {

    /**
     * 方法1
     * 可将s逆序再求和s的最长公共子序列串（参考LeetCode1143，本题不用此解法）
     */
    public static int longestPalindromeSubseq1(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        return process(str, 0, s.length() - 1);
    }

    private static int process(char[] str, int l, int r) {
        if (l == r) {
            return 1;
        }
        if (l == r - 1) {
            return str[l] == str[r] ? 2 : 1;
        }
//        int p1 = process(str, l + 1, r - 1);
        int p2 = process(str, l + 1, r);
        int p3 = process(str, l, r - 1);
        int p4 = str[l] == str[r] ? (process(str, l + 1, r - 1) + 2) : 0;
        return Math.max(Math.max(p2, p3), p4);
    }

    /**
     * dp
     */
    public static int longestPalindromeSubseq(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        int n = s.length();
        int[][] dp = new int[n][n];
        dp[n - 1][n - 1] = 1;
        for (int i = 0; i < n - 1; i++) {
            dp[i][i] = 1;
            dp[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
        }
        for (int i = n - 3; i >= 0; i--) {
            for (int j = i + 2; j < n; j++) {
                int p2 = dp[i + 1][j];
                int p3 = dp[i][j - 1];
                int p4 = str[i] == str[j] ? (dp[i + 1][j - 1] + 2) : 0;
                dp[i][j] = Math.max(Math.max(p2, p3), p4);
            }
        }
        return dp[0][n - 1];
    }

    public static void main(String[] args) {
        System.out.println(longestPalindromeSubseq("bbbab"));   // 4
        System.out.println(longestPalindromeSubseq("cbbd"));    // 2
    }
}
